package tree;

import sun.security.util.Length;

import java.util.HashMap;
import java.util.Map;

public class _105_从前序与中序遍历序列构造二叉树 {
    int[] preorder;
    int[] inorder;

    int preIndex = 0;
    Map<Integer, Integer> inOrderMap = new HashMap<>();

    public TreeNode buildTree2(int[] preorder, int[] inorder){
        if (preorder.length==0 || inorder.length!=preorder.length) {
            return null;
        }

        for (int i = 0; i < inorder.length; i++) {
            inOrderMap.put(inorder[i], i);
        }
        return doBuild1(0, preorder.length, preorder);
    }

    private TreeNode doBuild1(int start, int end, int[] preorder) {
        if (start>end) {
            return null;
        }
        int rootVal = preorder[preIndex++];
        Integer rootIndex = inOrderMap.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        root.left = doBuild1(start, rootIndex-1, preorder);
        root.right = doBuild1(rootIndex+1, end, preorder);
        return root;
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;

        int inOrderStart = 0;
        for (int i : inorder) {
            inOrderMap.put(i, inOrderStart++);
        }

        return help(0, inorder.length-1);

    }

    private TreeNode help(int inLeft, int inRight) {
        if (inLeft > inRight) {
            return null;
        }
        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);

        Integer integer = inOrderMap.get(rootVal);

        root.left = help(inLeft, integer-1);
        root.right = help(integer +1, inRight);
        return root;
    }

    private static int preIndex1 = 0;
    public static TreeNode buildTree1(int[] preorder, int[] inorder) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return doBuild(0, inorder.length-1, map, preorder, inorder);
    }

    private static TreeNode doBuild(int start, int end, Map<Integer, Integer> map, int[] preorder, int[] inorder) {
        if (start>end) {
            return null;
        }

        int rootVal = preorder[preIndex1++];
        Integer rootIdx = map.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        root.left = doBuild(start, rootIdx-1, map, preorder, inorder);
        root.right = doBuild(rootIdx+1, end, map, preorder, inorder);
        return root;
    }

    public static void main(String[] args) {
        TreeNode treeNode = buildTree1(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
    }


}
